#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : BinaryTreeInorderTraversal.py
# @Time    : 2020/9/14 9:51
# @Description:
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        """
        Given a binary tree, return the inorder traversal of its nodes' values.

        Example:
            Input: [1,null,2,3]
               1
                \
                 2
                /
               3

            Output: [1,3,2]
        Follow up: Recursive solution is trivial, could you do it iteratively?

        :param root:
        :return:
        """
        ans = []

        def helper(root: TreeNode):
            if root is not None:
                helper(root.left)
                ans.append(root.val)
                helper(root.right)
            return

        helper(root)
        return ans

    def inorderTraversal2(self, root: TreeNode) -> List[int]:
        from collections import deque
        queue = deque([root])
        ans = []
        while queue:
            node = queue.popleft()
            if node is not None:
                if isinstance(node, TreeNode):
                    queue.appendleft(node.right)
                    queue.appendleft(node.val)
                    queue.appendleft(node.left)
                else:
                    ans.append(node)
        return ans


if __name__ == '__main__':
    S = Solution()
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    print(S.inorderTraversal(root))
    print(S.inorderTraversal2(root))
    print('done')
